package real.bytedance.dynamic;

public class LongestPrinSubString {
    public String longestPalindrome(String s) {
        int len = 0;
        if (s == null || (len = s.length()) <= 1) return s;

        //f[i][j] 表示字符串下標從i到j是不是回文子串【暗含的意思是：j >= i】
        boolean[][] f = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            f[i][i] = true; //單個字符肯定是回文子串
        }
        int max = 1, start = 0;
        for (int j = 0; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (i == j) continue;
                else if (i == j - 1) {
                    //i, j只相割一個位置
                    f[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    //只有兩邊字符相等，且中間是回文子串，才是回文子串
                    f[i][j] = f[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                }
                if (f[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start + max);
    }

    public static void main(String[] args) {
        LongestPrinSubString lon = new LongestPrinSubString();
        String res = lon.longestPalindrome("cbbd");
        System.out.println(res);
    }
}
